package lib

//link to 282 416
func init() {
	Probs = append(Probs, Problem{
		Num:         494,
		Discription: "给非负整数数组添加+-，使得表达式等于目标值的数目",
		Level:       2,
		Labels: map[string]int{
			"0-1背包": 1,
			"动态规划": 1,
		},
	})
}

//转化成：从数组里选一些数字，把这些数字前面变成符号，再相加，等于target的个数
func FindTargetSumWays(nums []int, target int) int {
	sum := 0
	for i := range nums {
		sum += nums[i]
	}

	//设neg为符号变为负数的数的和，有如下等式（sum-neg）- neg = target，根据neg = (sum-target)/2能推出neg的值，以及两个条件
	if sum < target || (sum-target)%2 != 0 {
		return 0
	}

	negSum := (sum - target) / 2
	//dp[i][tempSum]表示从nums[:i]中选出一些符号为负的数，让nums[:i]加起来等于tempSum的个数
	dp := make([][]int, len(nums)+1)
	for i := range dp {
		dp[i] = make([]int, negSum+1)
	}
	//优先对negSum为0的情况进行处理
	dp[0][0] = 1
	for i := 1; i <= len(nums); i++ {
		if nums[i-1] == 0 {
			dp[i][0] = 2 * dp[i-1][0]
		} else {
			dp[i][0] = dp[i-1][0]
		}
	}

	for i := 1; i <= len(nums); i++ {
		for tempSum := 1; tempSum <= negSum; tempSum++ {
			if nums[i-1] > tempSum {
				dp[i][tempSum] = dp[i-1][tempSum]
			} else {
				dp[i][tempSum] = dp[i-1][tempSum-nums[i-1]] + dp[i-1][tempSum]
			}
		}
	}

	return dp[len(nums)][negSum]
}